package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/9/20 11:14
 */
public class _122_买卖股票的最佳时机 {
    public static void main(String[] args) {
        int[] num = new int[]{7,1,5,3,6,4};
//        int[] num = new int[]{7, 6, 4, 3, 1};
        System.err.println(maxProfit2(num));
    }

    /**
     * 贪心算法
     * > 2022/09/20 14:32:30
     * 解答成功:
     * 	执行耗时:1 ms,击败了81.77% 的Java用户
     * 	内存消耗:41.3 MB,击败了60.70% 的Java用户
     * @Description 局部利益最大化，形成整体利益最大化。贪心思想
     * @Author Ding
     * @Date 2022/9/20 14:33
     * @param prices 价格数组
     * @return int
     **/
    public static int maxProfit(int[] prices) {
        //由于要调用明天的，所以长度不满足两天及以上就直接return 0
        if (prices.length <= 1) {
            return 0;
        }
        //定义累加最大值
        int sumMax = 0;
        //定义分片最大值（局部<单笔股票>最大值）
        int dynamicMax = 0;
        //定义动态差（明天和今天的差）
        int dynamicVal = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            dynamicVal = prices[i + 1] - prices[i];
            if (dynamicVal > 0) {
                //明天比今天值钱，就能买
                dynamicMax += dynamicVal;
            } else {
                //明天不值钱了，今天就得卖。累加最大值+局部最大值。局部最大值置0
                sumMax += dynamicMax;
                dynamicMax = 0;
            }
        }
        //因为可能最后一天还是赚的，但是也要卖了。我们省略卖的步骤，直接返回sumMax+当前动态最大值，比如[1,2,3,4,5]，买的时候1块钱，卖的时候5块钱
        return sumMax + dynamicMax;
    }

    /**
     * 贪心最简单的解决办法
     * @Description
     * @Author Ding
     * @Date 2022/9/20 15:12
     * @param prices 价格数组
     * @return int
     **/
    public static int maxProfit2(int[] prices){
        int max = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            //如果明天比今天赚钱，就卖出，否则重置，且累加0
            max += Math.max(0,prices[i+1]-prices[i]);
        }
        return max;
    }
}
